package sort;

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;

/**
 * @author XY
 * @version 1.0
 * @date 2022/2/11 9:12
 * @Description
 */
public class Leet169 {
    public static int majorityElement(int[] nums) {
        Map<Integer,Integer> map =new HashMap<>();
        for (int num : nums) {
            Set<Integer> integers = map.keySet();
            if(!integers.contains(num)){
                map.put(num,1);
            }else{
                map.put(num,map.get(num)+1);
            }
        }
        Set<Map.Entry<Integer, Integer>> entries = map.entrySet();
        Iterator<Map.Entry<Integer, Integer>> iterator = entries.iterator();
        while (iterator.hasNext()){
            Map.Entry<Integer, Integer> next = iterator.next();
            if(next.getValue()>nums.length/2){
                return next.getKey();
            }
        }

        return -1;
    }

    //解法3：摩尔投票法
    //摩尔投票法，遇到相同的数，就投一票，遇到不同的数，就减一票，最后还存在票的数就是众数
    public int majorityElement1(int[] nums) {
        int count = 0;
        Integer candidate = null;

        for (int num : nums) {
            if (count == 0) {
                candidate = num;
            }
            count += (num == candidate) ? 1 : -1;
        }

        return candidate;
    }

    public static void main(String[] args) {
        int[] arr = {3,2,3};
        System.out.println(majorityElement(arr));
    }
}
